package com.example.algorithm.no0162.solution;

import com.example.algorithm.no0162.Solution;

/**
 * @Description 解答-寻找峰值-二分查找
 * 时间复杂度: O(log_2(n))。每一步都将搜索空间减半。因此，总的搜索空间只需要 log_2(n)步。其中 n 为 nums 数组的长度。
 * 空间复杂度: O(log_2(n))。每一步都将搜索空间减半。因此，总的搜索空间只需要 log_2(n)步。于是，递归树的深度为 log_2(n)。
 * @ClassName SolutionImpl
 * @Author Administrator
 * @Date 2020/5/20 10:26
 * @Version 1.0.0
 */
public class BinSearchSolutionImpl implements Solution {
    @Override
    public int findPeakElement(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }

    public int search(int[] nums, int l, int r) {
        if (l == r)
            return l;
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1])
            return search(nums, l, mid);
        return search(nums, mid + 1, r);
    }
}
